package com.mlh.dp.子序列;

/**
 * @author 缪林辉
 * @date 2024/5/21 11:40
 * @DESCRIPTION
 */
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组是数组中的一个连续部分。
public class 最大子数组和 {
    //这题可以用贪心，贪心做过类似的
    public int method1(int[] nums) {
        //dp[i]定义为以i结尾的连续子数组的最大和
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int res=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i-1]<0){//如果前面的子数组最大和是负数，直接丢掉自己新开一个，加上他只会让自己更小
                dp[i]=nums[i];
            }else{
                dp[i]=dp[i-1]+nums[i];
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }

    public int practice(int[] nums) {
        int[]dp=new int[nums.length];
        dp[0]=nums[0];
        int res=nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(dp[i-1]<0){
                dp[i]=nums[i];
            }else{
                dp[i]=dp[i-1]+nums[i];
            }
            res=Math.max(dp[i],res);
        }
        return res;
    }

    public int practice2(int[] nums) {
        int res=nums[0];
        int stageMax=0;
        for (int i = 0; i < nums.length; i++) {
            if(stageMax<=0){
                stageMax=nums[i];
            }else{
                stageMax+=nums[i];
            }
            res=Math.max(stageMax,res);
        }
        return res;
    }
}
